{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Swim in Rising Water"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #binary-search #matrix #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #二分查找 #矩阵 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: swimInWater"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #水位上升的泳池中游泳"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个 <code>n x n</code>&nbsp;的整数矩阵&nbsp;<code>grid</code> 中，每一个方格的值 <code>grid[i][j]</code> 表示位置 <code>(i, j)</code> 的平台高度。</p>\n",
    "\n",
    "<p>当开始下雨时，在时间为&nbsp;<code>t</code>&nbsp;时，水池中的水位为&nbsp;<code>t</code>&nbsp;。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。</p>\n",
    "\n",
    "<p>你从坐标方格的左上平台&nbsp;<code>(0，0)</code> 出发。返回 <em>你到达坐标方格的右下平台&nbsp;<code>(n-1, n-1)</code>&nbsp;所需的最少时间 。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/29/swim1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[0,2],[1,3]]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>\n",
    "时间为0时，你位于坐标方格的位置为 <code>(0, 0)。</code>\n",
    "此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。\n",
    "等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]\n",
    "<strong>输出:</strong> 16\n",
    "<strong>解释: </strong>最终的路线用加粗进行了标记。\n",
    "我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;&nbsp;n<sup>2</sup></code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;中每个值&nbsp;<strong>均无重复</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [swim-in-rising-water](https://leetcode.cn/problems/swim-in-rising-water/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [swim-in-rising-water](https://leetcode.cn/problems/swim-in-rising-water/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,2],[1,3]]', '[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        time = 0\n",
    "        dirs = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        visited = set()\n",
    "        elevations = defaultdict(set)\n",
    "        elevations[grid[0][0]].add((0,0))\n",
    "        def dfs(i,j):\n",
    "            visited.add((i,j))\n",
    "            for d in dirs:\n",
    "                di,dj = i+d[0], j+d[1]\n",
    "                if (di,dj) not in visited and 0<=di<n and 0<=dj<n:\n",
    "                    elev = grid[di][dj]\n",
    "                    if elev>time:\n",
    "                        elevations[elev].add((di,dj))\n",
    "                    else:\n",
    "                        dfs(di,dj)\n",
    "\n",
    "        while True:\n",
    "            if time in elevations:\n",
    "                for i,j in elevations[time]:\n",
    "                    dfs(i,j)\n",
    "                del elevations[time]\n",
    "                if (n-1,n-1) in visited:\n",
    "                    return time\n",
    "            time+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 方法一：heap\n",
    "        N = len(grid)\n",
    "        heap = []\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        heapq.heappush(heap, (grid[0][0], 0, 0))\n",
    "        visited.add(grid[0][0])\n",
    "        while heapq:\n",
    "            cur, x, y = heapq.heappop(heap)\n",
    "            ans = max(ans, cur)\n",
    "            if cur == grid[-1][-1]:\n",
    "                return ans\n",
    "            for dx, dy in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0<=nx<N and 0<=ny<N and grid[nx][ny] not in visited:\n",
    "                    visited.add(grid[nx][ny])\n",
    "                    heapq.heappush(heap, (grid[nx][ny], nx, ny))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n, dir = len(grid), ((1, -1, 0, 0), (0, 0, 1, -1))\n",
    "        if grid[0][0] == n * n - 1 or grid[n-1][n-1] == n * n - 1:\n",
    "            return n * n - 1\n",
    "        par, rank, pos = [i for i in range(n * n)], n * n * [0], n * n * [0]\n",
    "\n",
    "        def hashVal(r, c):\n",
    "            return r * n + c\n",
    "        def find(x):\n",
    "            if x == par[x]:\n",
    "                return x\n",
    "            else:\n",
    "                par[x] = find(par[x])\n",
    "                return par[x]\n",
    "        def unite(x, y):\n",
    "            x = find(x)\n",
    "            y = find(y)\n",
    "            if x == y:\n",
    "                return\n",
    "            if rank[x] < rank[y]:\n",
    "                par[x] = y\n",
    "            else:\n",
    "                par[y] = x\n",
    "                if rank[x] == rank[y]:\n",
    "                    rank[x] += 1\n",
    "        def same(x, y):\n",
    "            return find(x) == find(y)\n",
    "        def inSide(r, c):\n",
    "            return 0 <= r and r < n and 0 <= c and c < n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pos[grid[i][j]] = hashVal(i, j)\n",
    "        #print(pos)\n",
    "        for i in range(n * n):\n",
    "            r, c = pos[i] // n, pos[i] % n\n",
    "            for j in range(4):\n",
    "                nearR, nearC = r + dir[0][j], c + dir[1][j]\n",
    "                if inSide(nearR, nearC) and grid[nearR][nearC] < i:\n",
    "                    unite(hashVal(nearR, nearC), hashVal(r, c))\n",
    "            if same(0, n * n - 1):\n",
    "                return i\n",
    "        return n * n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        size = len(grid)\n",
    "        reachablePoints = { self.keyOfPoints((0, 0)): (0, 0) }    \n",
    "        t = grid[0][0]\n",
    "        \n",
    "        while True:\n",
    "            stack = list(reachablePoints.values())\n",
    "            stackDict = reachablePoints.copy()\n",
    "            while len(stack) > 0:\n",
    "                point = stack.pop()\n",
    "                reachablePoints[self.keyOfPoints(point)] = point\n",
    "                \n",
    "                left = (point[0] - 1, point[1])\n",
    "                right = (point[0] + 1, point[1])\n",
    "                up = (point[0], point[1] - 1)\n",
    "                down = (point[0], point[1] + 1)\n",
    "                points = [left, right, up, down]\n",
    "                \n",
    "                for p in points:\n",
    "                    if p[0] >= 0 and p[0] < size and p[1] >= 0 and p[1] < size and grid[p[0]][p[1]] <= t and self.keyOfPoints(p) not in stackDict:\n",
    "                        print(\"reach new point \" + str(p) + \" when \" + str(t))\n",
    "                        if p[0] == size - 1 and p[1] == size - 1:\n",
    "                            return t;\n",
    "                        stack.insert(0, p)\n",
    "                        stackDict[self.keyOfPoints(p)] = p\n",
    "            \n",
    "            t += 1\n",
    "                        \n",
    "        return t\n",
    "            \n",
    "    def keyOfPoints(self, point):\n",
    "        return str(point[0]) + \",\" + str(point[1])\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(grid)\n",
    "        if l == 1: return grid[0][0]\n",
    "        start = max(grid[0][0], min(grid[-1][-2], grid[-2][-1]), grid[-1][-1])\n",
    "        if l == 2: return start\n",
    "        #\n",
    "        father = {}  # 并查集\n",
    "        def _find(x):\n",
    "            if x not in father: father[x] = x\n",
    "            if father[x] != x: father[x] = _find(father[x])\n",
    "            return father[x]\n",
    "        def _union(x, y):\n",
    "            father[_find(x)] = _find(y)\n",
    "        #\n",
    "        pos = {(x, y) for x in range(l) for y in range(l)}\n",
    "        def _connect(t):\n",
    "            for i, j in pos.copy():\n",
    "                if grid[i][j] <= t:\n",
    "                    pos.remove((i, j))\n",
    "                    if i > 0 and grid[i - 1][j] <= t:\n",
    "                        _union((i, j), (i - 1, j))\n",
    "                    if i < l - 1 and grid[i + 1][j] <= t:\n",
    "                        _union((i, j), (i + 1, j))\n",
    "                    if j > 0 and grid[i][j - 1] <= t:\n",
    "                        _union((i, j), (i, j - 1))\n",
    "                    if j < l - 1 and grid[i][j + 1] <= t:\n",
    "                        _union((i, j), (i, j + 1))\n",
    "        #\n",
    "        while True:\n",
    "            _connect(start)\n",
    "            if _find((0, 0)) == _find((l - 1, l - 1)):\n",
    "                break\n",
    "            start += 1\n",
    "        \n",
    "        return start\n",
    "            \n",
    "        \n",
    "                        \n",
    "                        \n",
    "                        \n",
    "                        \n",
    "                        \n",
    "                        \n",
    "                        \n",
    "                        \n",
    "                        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(grid)\n",
    "        pas = [[0 for j in range(l)] for i in range(l)]\n",
    "        path = [[[] for j in range(l)] for i in range(l)]\n",
    "        for i in range(l):\n",
    "            for j in range(l):\n",
    "                n = grid[i][j]\n",
    "                if i > 0:\n",
    "                    path[i][j].append([i - 1, j])\n",
    "                if j > 0:\n",
    "                    path[i][j].append([i, j-1])\n",
    "                if i < l - 1:\n",
    "                    path[i][j].append([i + 1, j])\n",
    "                if j < l - 1:\n",
    "                    path[i][j].append([i, j+1])\n",
    "\n",
    "        stack = [[grid[0][0], 0, 0]]\n",
    "        while True:\n",
    "            n = stack.pop(0)\n",
    "            if pas[n[1]][n[2]] != 0: continue\n",
    "            if n[1] == l - 1 and n[2] == l - 1: return n[0]\n",
    "            pas[n[1]][n[2]]=1\n",
    "            for i in path[n[1]][n[2]]:\n",
    "                if pas[i[0]][i[1]] != 0: continue\n",
    "                bisect.insort_left(stack, [max(grid[i[0]][i[1]],n[0]), i[0], i[1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 方法二：二分查找 + dfs\n",
    "        # time complexity: O(n^2logn), space compelxity: O(n^2)\n",
    "        N = len(grid)\n",
    "        left, right = max(grid[0][0], grid[-1][-1]), N**2-1\n",
    "        def dfs(start):\n",
    "            if start == (N-1, N-1):\n",
    "                return True\n",
    "            visited.add(start)\n",
    "            x, y = start\n",
    "            for dx, dy in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0<=nx<N and 0<=ny<N and (nx,ny) not in visited and grid[nx][ny] <= mid:\n",
    "                    if dfs((nx, ny)):\n",
    "                        return True\n",
    "            return False\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            visited = set()\n",
    "            if dfs((0, 0)):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 方法二：二分查找 + dfs\n",
    "        # time complexity: O(n^2logn), space compelxity: O(n^2)\n",
    "        N = len(grid)\n",
    "        left, right = max(grid[0][0], grid[-1][-1]), N**2-1\n",
    "        def dfs(start):\n",
    "            visited.add(start)\n",
    "            x, y = start\n",
    "            for dx, dy in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0<=nx<N and 0<=ny<N and (nx,ny) not in visited and grid[nx][ny] <= mid:\n",
    "                    dfs((nx, ny))\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            visited = set()\n",
    "            dfs((0, 0))\n",
    "            if (N-1, N-1) in visited:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def swimInWater(self, grid):\n",
    "        N = len(grid)\n",
    "\n",
    "        seen = {(0, 0)}\n",
    "        pq = [(grid[0][0], 0, 0)]\n",
    "        ans = 0\n",
    "        while pq:\n",
    "            d, r, c = heapq.heappop(pq)\n",
    "            ans = max(ans, d)\n",
    "            if r == c == N-1: return ans\n",
    "            for cr, cc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):\n",
    "                if 0 <= cr < N and 0 <= cc < N and (cr, cc) not in seen:\n",
    "                    heapq.heappush(pq, (grid[cr][cc], cr, cc))\n",
    "                    seen.add((cr, cc))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        row_len = len(grid)\n",
    "        col_len = len(grid[0])\n",
    "        dp = []\n",
    "        for i in range(row_len):\n",
    "            dp.append([0] * col_len)\n",
    "        reachable_stack = [[0, 0]]\n",
    "        result = 0\n",
    "        while reachable_stack:\n",
    "            reachable_grid = reachable_stack.pop()\n",
    "            row, col = reachable_grid[0], reachable_grid[1]\n",
    "            dp[row][col] = 1\n",
    "            result = max(result, grid[row][col])\n",
    "            if row == row_len-1 and col == col_len-1:\n",
    "                break\n",
    "            for direction in directions:\n",
    "                new_row, new_col = row + direction[0], col + direction[1]\n",
    "                if 0 <= new_row < row_len and 0 <= new_col < col_len and not dp[new_row][new_col]:\n",
    "                    dp[new_row][new_col] = 1\n",
    "                    reachable_stack.append([new_row, new_col])\n",
    "            reachable_stack = sorted(reachable_stack, key = lambda x:grid[x[0]][x[1]], reverse = True)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        passed = [[0, 0]]\n",
    "        len_g = len(grid)\n",
    "        result = grid[len(grid) - 1][len(grid[0]) - 1]\n",
    "        pq = [[grid[0][0], 0, 0]]\n",
    "        \n",
    "        while pq:\n",
    "            pq.sort()\n",
    "            tmp, s, c = pq[0][0], pq[0][1], pq[0][2]\n",
    "            result = max(result, tmp)\n",
    "            pq.pop(0)\n",
    "            if s == c == (len_g - 1): return result\n",
    "            for sow, col in ((s + 1, c), (s - 1, c), (s, c + 1), (s, c - 1)):\n",
    "                if 0 <= sow < len_g and 0 <= col < len_g and [sow, col] not in passed:\n",
    "                    pq.append([grid[sow][col], sow, col])\n",
    "                    passed.append([sow, col])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        max_val=0\n",
    "        if len(grid)>0 and len(grid[0])>0:\n",
    "            heap=[(grid[0][0],0,0)]\n",
    "            visited=[[False]*len(grid) for i in range(len(grid[0]))]\n",
    "            visited[0][0]=True\n",
    "            moves=[(-1,0),(0,1),(1,0),(0,-1)]\n",
    "            while len(heap)>0:\n",
    "                cur_val,x,y=heapq.heappop(heap)\n",
    "                max_val=max(cur_val,max_val)\n",
    "                if x==len(grid)-1 and y==len(grid[0])-1:\n",
    "                    break\n",
    "                for dx,dy in moves:\n",
    "                    next_x,next_y=x+dx,y+dy\n",
    "                    if 0<=next_x<len(grid) and 0<=next_y<len(grid[0]) and not visited[next_x][next_y]:\n",
    "                        visited[next_x][next_y]=True\n",
    "                        heapq.heappush(heap,(grid[next_x][next_y],next_x,next_y))\n",
    "        return max_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "        length = len(grid)\n",
    "        mark = [[0 for _ in range(length)] for _ in range(length)]\n",
    "        heap = [(grid[0][0], 0, 0)]\n",
    "        mark[0][0] = 1\n",
    "        hmax=0\n",
    "        while heap:\n",
    "            h, i, j = heapq.heappop(heap)\n",
    "            for x, y in ((i+1,j), (i,j+1), (i-1,j), (i,j-1)):\n",
    "                if -1 < x < length and -1 < y < length and mark[x][y] == 0:\n",
    "                    mark[x][y] = 1\n",
    "                    if h > hmax:\n",
    "                        hmax=h\n",
    "                    if mark[length-1][length-1] == 1:\n",
    "                        return max(grid[x][y], hmax)\n",
    "                    heapq.heappush(heap, (grid[x][y], x, y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        self.grid = grid\n",
    "        N = len(grid)\n",
    "\n",
    "        left = grid[0][0]\n",
    "        right = N*N\n",
    "\n",
    "        while(left < right):\n",
    "            mid = (left+right)//2\n",
    "            if self.GetPossible(mid):\n",
    "                right = mid \n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left \n",
    "    \n",
    "    def GetPossible(self, T):\n",
    "        st1 = [(0, 0)]\n",
    "        st2 = [(0, 0)]\n",
    "\n",
    "        while st1:\n",
    "            r, c = st1.pop()\n",
    "            if r==c==len(self.grid)-1:\n",
    "                    return True\n",
    "            for r, c in ([(r-1, c), (r+1, c), (r, c+1), (r, c-1)]):\n",
    "                \n",
    "                if r>=0 and r<len(self.grid) and c>=0 and c <len(self.grid) and (r, c) not in st2 and self.grid[r][c]<=T:\n",
    "                    st1.append((r,c))\n",
    "                    st2.append((r,c))\n",
    "        return False\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        seen = {(0,0)}\n",
    "        heap = [(grid[0][0], 0, 0)]\n",
    "        ans = 0\n",
    "        while heap:\n",
    "            h, r, c = heapq.heappop(heap)\n",
    "            ans = max(h, ans)\n",
    "            seen.add((r, c))\n",
    "            if r == n-1 and c == n-1:\n",
    "                return ans\n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, 1), (0,-1)]:\n",
    "                nr = r + dx\n",
    "                nc = c + dy\n",
    "                if 0<= nr < n and 0<= nc < n and (nr, nc) not in seen:\n",
    "                    heapq.heappush(heap, (grid[nr][nc], nr, nc))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        seen = {(0,0)}\n",
    "        \n",
    "        def possible(T):\n",
    "            stack = [(0, 0)]\n",
    "            seen = {(0, 0)}\n",
    "            while stack:\n",
    "                r, c = stack.pop()\n",
    "                seen.add((r,c))\n",
    "                if r == c == n-1: return True\n",
    "                for x, y  in [(1,0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    nr = x+r\n",
    "                    nc = y+c\n",
    "                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] <= T and (nr, nc) not in seen:\n",
    "                        stack.append((nr,nc))\n",
    "            return False\n",
    "\n",
    "        l, r = grid[0][0], n*n\n",
    "        while r > l:\n",
    "            mid = l + (r-l) // 2\n",
    "            if possible(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        # 二分\n",
    "        N = len(grid)\n",
    "        l,r = max(grid[-1][-1],grid[0][0]),N*N-1\n",
    "        def bfs(x,y,h):\n",
    "            q = [[x,y]]\n",
    "            visited = [[False]*N for _ in range(N)]\n",
    "            while(q):\n",
    "                a,b = q.pop(0)\n",
    "                if a==N-1 and b==N-1:\n",
    "                    return True \n",
    "                for i,j in [[a+1,b],[a-1,b],[a,b-1],[a,b+1]]:\n",
    "                    if 0<=i<N and 0<=j<N and grid[i][j] <= h and not visited[i][j]:\n",
    "                        visited[i][j]=True \n",
    "                        q.append([i,j])\n",
    "            return False \n",
    "        while(l<=r):\n",
    "            mid = (l+r)//2\n",
    "            f = bfs(0,0,mid) \n",
    "            if f:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "            # print(l,r)\n",
    "        return r + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        import math,heapq\n",
    "        n = len(grid)\n",
    "        visited = [[0]*n for i in range(n)]\n",
    "        dq = []\n",
    "        dq.append([0,0])\n",
    "        dist = [[math.inf]*n for i in range(n)]\n",
    "        dist[0][0]=grid[0][0]\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        while(dq):\n",
    "\n",
    "            front = heapq.nsmallest(1,dq,lambda x: grid[x[0]][x[1]])[0]\n",
    "            # dq.sort(key=lambda x: grid[x[0]][x[1]],reverse=True)\n",
    "            # front = dq.pop()\n",
    "            dq.remove(front)\n",
    "            #dq.remove(front)\n",
    "            currentX = front[0]\n",
    "            currentY = front[1]\n",
    "            if visited[currentX][currentY]:continue\n",
    "            visited[currentX][currentY] = 1\n",
    "            if currentX==n-1 and currentY==n-1:\n",
    "                return dist[n-1][n-1]\n",
    "            for direction in directions:\n",
    "                newX = currentX + direction[0]\n",
    "                newY = currentY + direction[1]\n",
    "                if self.inArea(newX,newY,n) and (not visited[newX][newY]) and max(dist[currentX][currentY],grid[newX][newY])<dist[newX][newY]:\n",
    "                    dist[newX][newY] = max(dist[currentX][currentY],grid[newX][newY])\n",
    "                    dq.append([newX,newY])\n",
    "\n",
    "\n",
    "\n",
    "    def inArea(self,x,y,n):\n",
    "        return x>=0 and x <n and y>=0 and y<n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        pq = [(grid[0][0], 0, 0)]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        visited[0][0] = False\n",
    "        while len(pq) > 0:\n",
    "            time, x, y = heapq.heappop(pq)\n",
    "            if x == m-1 and y == n-1:\n",
    "                return time\n",
    "            if visited[x][y]:\n",
    "                continue\n",
    "            visited[x][y] = True\n",
    "            for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[nx][ny]:\n",
    "                    continue\n",
    "\n",
    "                heapq.heappush(pq, (max(time, grid[nx][ny]), nx, ny))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "MOVES = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self,\n",
    "                 grid: List[List[int]],\n",
    "                 n: int,\n",
    "                 t: int) -> bool:\n",
    "        if t < grid[-1][-1] or t < grid[0][0]:\n",
    "            return False\n",
    "        visited = [[False] * n for _ in range(n)]\n",
    "        q = deque([(0, 0)])\n",
    "        visited[0][0] = True\n",
    "        while q:\n",
    "            x, y = q.pop()\n",
    "            if (x, y) == (n - 1, n - 1):\n",
    "                return True\n",
    "            for dx, dy in MOVES:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < n and 0 <= ny < n) \\\n",
    "                        or visited[nx][ny] \\\n",
    "                        or grid[nx][ny] > t:\n",
    "                    continue\n",
    "                q.appendleft((nx, ny))\n",
    "                visited[nx][ny] = True\n",
    "        return False\n",
    "\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        l, r = 0, n * n\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if self.canReach(grid, n, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        if self.canReach(grid, n, l):\n",
    "            return l\n",
    "        else:\n",
    "            return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "MOVES = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self,\n",
    "                 grid: List[List[int]],\n",
    "                 n: int,\n",
    "                 t: int) -> bool:\n",
    "        if t < grid[-1][-1] or t < grid[0][0]:\n",
    "            return False\n",
    "        front_q, back_q = deque([(0, 0)]), deque([(n - 1, n - 1)])\n",
    "        front_vis, back_vis = {(0, 0)}, {(n - 1, n - 1)}\n",
    "        while front_q and back_q:\n",
    "            x, y = front_q.pop()\n",
    "            if (x, y) in back_vis:\n",
    "                return True\n",
    "            for dx, dy in MOVES:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < n and 0 <= ny < n) \\\n",
    "                        or grid[nx][ny] > t \\\n",
    "                        or (nx, ny) in front_vis:\n",
    "                    continue\n",
    "                front_q.appendleft((nx, ny))\n",
    "                front_vis.add((nx, ny))\n",
    "            x, y = back_q.pop()\n",
    "            if (x, y) in front_vis:\n",
    "                return True\n",
    "            for dx, dy in MOVES:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < n and 0 <= ny < n) \\\n",
    "                        or grid[nx][ny] > t \\\n",
    "                        or (nx, ny) in back_vis:\n",
    "                    continue\n",
    "                back_q.appendleft((nx, ny))\n",
    "                back_vis.add((nx, ny))\n",
    "        return False\n",
    "\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        l, r = 0, n * n\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if self.canReach(grid, n, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        if self.canReach(grid, n, l):\n",
    "            return l\n",
    "        else:\n",
    "            return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution(object):\n",
    "#     def swimInWater(self, grid):\n",
    "#         n = len(grid)\n",
    "#         dirs = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "\n",
    "#         def next_move(i, j):\n",
    "#             for dx, dy in dirs:\n",
    "#                 x, y = i+dx, j+dy\n",
    "#                 if 0<=x<n and 0<=y<n and (x,y) not in seen:\n",
    "#                     seen.add((x,y))\n",
    "#                     yield x,y\n",
    "        \n",
    "#         seen = {(0, 0)}\n",
    "#         pq = [(grid[0][0], 0, 0)]\n",
    "#         ans = 0\n",
    "#         while pq:\n",
    "#             t, i, j = heapq.heappop(pq)\n",
    "#             ans = max(ans, t)\n",
    "#             if i == j == n-1: \n",
    "#                 return ans\n",
    "#             for x, y in next_move(i, j):\n",
    "#                 heapq.heappush(pq, (grid[x][y], x, y))\n",
    "\n",
    "\n",
    "# class Solution(object):\n",
    "#     def swimInWater(self, grid):\n",
    "#         n = len(grid)\n",
    "#         dirs = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "\n",
    "#         def possible(T):\n",
    "#             stack = [(0, 0)]\n",
    "#             seen = {(0, 0)}\n",
    "\n",
    "#             def next_move(i, j):\n",
    "#                 for dx, dy in dirs:\n",
    "#                     x, y = i+dx, j+dy\n",
    "#                     if 0<=x<n and 0<=y<n and (x,y) not in seen and grid[x][y]<=T:\n",
    "#                         seen.add((x,y))\n",
    "#                         yield x,y\n",
    "\n",
    "#             while stack:\n",
    "#                 i, j = stack.pop()\n",
    "#                 if i == j == n-1: \n",
    "#                     return True\n",
    "#                 for x, y in next_move(i, j):\n",
    "#                     stack.append((x, y))\n",
    "#             return False\n",
    "\n",
    "#         lo, hi = grid[0][0], n * n\n",
    "#         while lo <= hi:\n",
    "#             mid = (lo+hi) // 2\n",
    "#             if possible(mid):\n",
    "#                 hi = mid - 1\n",
    "#             else:\n",
    "#                 lo = mid + 1\n",
    "#         return lo\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        parents = list(range(n * n))\n",
    "        ranks = [1] * (n * n)\n",
    "        \n",
    "        def find(id: int) -> int:\n",
    "            while id != parents[id]:\n",
    "                parents[id] = parents[parents[id]]\n",
    "                id = parents[id]\n",
    "            return id\n",
    "\n",
    "        def union(a: int, b: int) -> None:\n",
    "            pa, pb = find(a), find(b)\n",
    "            if pa == pb:\n",
    "                return\n",
    "            if ranks[pa] <= ranks[pb]:\n",
    "                parents[pa] = pb\n",
    "                ranks[pb] += ranks[pa]\n",
    "            else:\n",
    "                parents[pb] = pa\n",
    "                ranks[pa] += ranks[pb]\n",
    "\n",
    "        # map_ = [0] * (n * n)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         map_[grid[i][j]] = i * n + j\n",
    "        map_ = {grid[i][j]: i * n + j for i in range(n) for j in range(n)}\n",
    "        \n",
    "        def next_move(i, j, T):\n",
    "            for dx, dy in dirs:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0<=x<n and 0<=y<n and (x,y) and grid[x][y]<=T:\n",
    "                    yield x,y\n",
    "\n",
    "        for time in range(n * n):\n",
    "            idx = map_[time]\n",
    "            i, j = divmod(idx, n)\n",
    "            print(time, idx)\n",
    "            for x, y in next_move(i,j, time):\n",
    "                union(idx, x * n + y)\n",
    "            # print(parents)\n",
    "            # print(ranks)\n",
    "            if find(0) == find(n * n - 1):\n",
    "                # print(parents)\n",
    "                # print(ranks)\n",
    "                return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if n == 1: return grid[0][0]\n",
    "        vis = [[0]*n for _ in range(n)]\n",
    "        cnt = 0\n",
    "        def check(h):\n",
    "            nonlocal cnt\n",
    "            if h < grid[0][0]: return False\n",
    "            q = deque([(0, 0)])\n",
    "            dx = [0, 0, 1, -1]\n",
    "            dy = [1, -1, 0, 0]\n",
    "            cnt += 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for i in range(4):\n",
    "                    nx, ny = x + dx[i], y + dy[i]\n",
    "                    if nx >= 0 and nx < n and ny>=0 and ny < n and grid[nx][ny] <= h and vis[nx][ny] != cnt:\n",
    "                        if nx == n - 1 and ny == n - 1: return True\n",
    "                        q.append((nx, ny))\n",
    "                        vis[nx][ny] = cnt\n",
    "            return False\n",
    "        \n",
    "        left, right = 0, max(max(row) for row in grid)\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        def bfs(xx):\n",
    "            q = deque()\n",
    "            q.append([0, 0])\n",
    "            n = len(grid)\n",
    "            st = [[0] * n for _ in range(n)]\n",
    "            dx = [-1, 0, 1, 0]\n",
    "            dy = [0, 1, 0, -1]\n",
    "            st[0][0] = 1\n",
    "            while q:\n",
    "                t = q.popleft()\n",
    "                if t == [n - 1, n - 1]: return True\n",
    "                x, y = t[0], t[1]\n",
    "                for i in range(4):\n",
    "                    a = x + dx[i]\n",
    "                    b = y + dy[i]\n",
    "                    if a >= 0 and a < n and b >= 0 and b < n and grid[a][b] <= xx and st[a][b] == 0:\n",
    "                        q.append([a, b])\n",
    "                        st[a][b] = 1\n",
    "            return False\n",
    "        l, r = grid[0][0], 2510\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if bfs(mid): r = mid \n",
    "            else: l = mid + 1\n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n = len(grid)\n",
    "        heap = [(grid[0][0],0,0)]\n",
    "        visited = set([(0,0)])\n",
    "        \n",
    "        while heap:\n",
    "            height,x,y = heapq.heappop(heap)\n",
    "            res = max(res,height)\n",
    "            if x == n-1 and y == n-1:\n",
    "                return res\n",
    "            \n",
    "            for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                new_x,new_y = x + dx,y + dy\n",
    "                if 0 <= new_x < n and 0 <= new_y < n and (new_x,new_y) not in visited:\n",
    "                    visited.add((new_x,new_y))\n",
    "                    heapq.heappush(heap,(grid[new_x][new_y],new_x,new_y))\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))\n",
    "        heap = [(grid[0][0], 0, 0)] # t, i, j\n",
    "        seen = set()\n",
    "        time = 0\n",
    "\n",
    "        while True:\n",
    "            if heap[0][0] > time:\n",
    "                time += 1\n",
    "                continue\n",
    "            t, i, j = heappop(heap)\n",
    "            if (i, j) == (n-1, n-1):\n",
    "                return time\n",
    "            seen.add((i, j))\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = dx + i, dy + j\n",
    "                if not (0 <= nx < n and 0 <= ny < n and (nx, ny) not in seen):\n",
    "                    continue\n",
    "                heappush(heap, (grid[nx][ny], nx, ny))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        par=[i for i in range(m*n)]\n",
    "        def find(x):\n",
    "            if x==par[x]:return x\n",
    "            return find(par[x])\n",
    "        def un(x,y):\n",
    "            rx,ry=find(x),find(y)\n",
    "            if rx==ry:return\n",
    "            par[ry]=rx\n",
    "        def isc(x,y):\n",
    "            return find(x)==find(y)\n",
    "        edgs=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos=i*n+j\n",
    "                d=grid[i][j]\n",
    "                if i+1<m:\n",
    "                    edgs.append((max(d,grid[i+1][j]),pos,pos+n))\n",
    "                if j+1<n:\n",
    "                    edgs.append((max(d,grid[i][j+1]),pos,pos+1))\n",
    "        edgs.sort(reverse=False)\n",
    "        # print(edgs)\n",
    "        for d,x,y in edgs:\n",
    "            un(x,y)\n",
    "            if isc(0,m*n-1):\n",
    "                return d\n",
    "            # else:\n",
    "            #     print(find(m*n-1))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 本质是求连通路径上的最大值\n",
    "'''\n",
    "# 方法一：二分法\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        left = grid[0][0] # 注意左边界\n",
    "        right = n * n\n",
    "        ans = 0\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            queue = [(0, 0)]\n",
    "            seen = {(0, 0)}\n",
    "            while queue:\n",
    "                i, j = queue.pop(0)\n",
    "                for new_i, new_j in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                    if 0 <= new_i < n and 0 <= new_j < n and (new_i, new_j) not in seen and grid[new_i][new_j] <= mid:\n",
    "                        queue.append((new_i, new_j))\n",
    "                        seen.add((new_i, new_j))\n",
    "            if (n-1, n-1) in seen:\n",
    "                ans = mid\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans\n",
    "'''\n",
    "\n",
    "# 并查集\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.count = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1\n",
    "    \n",
    "    def is_connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        # 构建权重\n",
    "        weights = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i < n - 1:\n",
    "                   x = i * n + j\n",
    "                   y = (i + 1) * n + j\n",
    "                   weight = max(grid[i][j], grid[i+1][j])\n",
    "                   weights.append([x, y, weight])\n",
    "                if j < n - 1:\n",
    "                    x = i * n + j\n",
    "                    y = i * n + j + 1\n",
    "                    weight = max(grid[i][j], grid[i][j+1])\n",
    "                    weights.append([x, y, weight])\n",
    "        weights.sort(key=lambda x: x[2])\n",
    "        # 使用并查集进行合并\n",
    "        union_find = UnionFind(n * n)\n",
    "        for weight in weights:\n",
    "            x = weight[0]\n",
    "            y = weight[1]\n",
    "            h = weight[2]\n",
    "            union_find.union(x, y)\n",
    "            if union_find.is_connect(0, n*n-1):\n",
    "                return h\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        parent = dict()\n",
    "        def find(a):\n",
    "            if parent[a] == a:\n",
    "                return parent[a]\n",
    "            else:\n",
    "                parent[a] = find(parent[a])\n",
    "                return parent[a]\n",
    "        def union(a, b):\n",
    "            parent[find(a)] = find(b)\n",
    "            #find(a)\n",
    "            \n",
    "        #parent[(0, 0)] = (0, 0)\n",
    "        cur = 0\n",
    "        while not ((0, 0) in parent and (n-1, n-1) in parent and find((n-1, n-1)) == find((0, 0))):\n",
    "            if cur >= n**2:\n",
    "                return -1\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == cur:\n",
    "                        parent[(i, j)] = (i, j)\n",
    "                        if i-1>=0 and (i-1, j) in parent:\n",
    "                            union((i, j), (i-1, j))\n",
    "                        if j-1>=0 and (i, j-1) in parent:\n",
    "                            union((i, j), (i, j-1))\n",
    "                        if i+1<=n-1 and (i+1, j) in parent:\n",
    "                            union((i, j), (i+1, j))\n",
    "                        if j+1<=n-1 and (i, j+1) in parent:\n",
    "                            union((i, j), (i, j+1))\n",
    "            cur += 1\n",
    "        return cur -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if f.setdefault(x,x)!=x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def union(x,y):\n",
    "            f[find(x)] = find(y)\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        f = {}\n",
    "        for t,i,j in sorted((grid[i][j],i,j) for i in range(m) for j in range(n)):\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y]<t:\n",
    "                    union((i,j),(x,y))\n",
    "            if find((0,0))==find((m-1,n-1)):\n",
    "                return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid):\n",
    "        n = len(grid)\n",
    "\n",
    "        def func(row, col, visited, height):\n",
    "            if self.switch == 1: return True\n",
    "            res = []\n",
    "            if row == col == 0 and grid[row][col] <= height:\n",
    "                res.append(True)\n",
    "                self.switch = 1\n",
    "            for i in [max(0, row - 1), min(row + 1, n - 1)]:\n",
    "                if grid[i][col] > height: res.append(False)\n",
    "                if grid[i][col] <= height and grid[i][col] not in visited:\n",
    "                    visited.append(grid[i][col])\n",
    "                    res.append(func(i, col, visited, height))\n",
    "            for j in [max(0, col - 1), min(col + 1, n - 1)]:\n",
    "                if grid[row][j] > height: res.append(False)\n",
    "                if grid[row][j] <= height and grid[row][j] not in visited:\n",
    "                    visited.append(grid[row][j])\n",
    "                    res.append(func(row, j, visited, height))\n",
    "            return True in res\n",
    "\n",
    "        l = 0\n",
    "        r = max(map(max, grid))\n",
    "        self.switch = 0\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if grid[n - 1][n - 1] <= mid:\n",
    "                self.switch = 0\n",
    "                s = set()\n",
    "                func(n - 1, n - 1, [grid[n - 1][n - 1]], mid)\n",
    "                if self.switch == 1:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        right = max(max(nums) for nums in grid)\n",
    "        left = 0\n",
    "        n = len(grid)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.dfs(grid, [[False] * n for _ in range(n)], 0, 0, mid):\n",
    "                # print(mid,True)\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                # print(mid,False)\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def dfs(self, grid: List[List[int]], visited: List[List[int]], x: int, y: int, t: int):\n",
    "        n = len(grid)\n",
    "        if x < 0 or x >= n or y >= n or y < 0 or visited[x][y] == True or grid[x][y] > t:\n",
    "            return False\n",
    "        if x == n - 1 and y == n - 1:\n",
    "            return True\n",
    "        visited[x][y] = True\n",
    "        return self.dfs(grid, visited, x + 1, y, t) or self.dfs(grid, visited, x - 1, y, t) or \\\n",
    "            self.dfs(grid, visited, x, y + 1, t) or self.dfs(grid, visited, x, y - 1, t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        def dfs(i: int, j: int, t: int) -> bool:\n",
    "            if dic[i][j] != 0 or grid[i][j] > t:\n",
    "                return False\n",
    "            dic[i][j] = 1\n",
    "            if i == n - 1 and j == n - 1:\n",
    "                return True\n",
    "            ans = False\n",
    "            if i - 1 >= 0: ans = ans or dfs(i - 1, j, t)\n",
    "            if i + 1 < n: ans = ans or dfs(i + 1, j, t)\n",
    "            if j - 1 >= 0: ans = ans or dfs(i, j - 1, t)\n",
    "            if j + 1 < n: ans = ans or dfs(i, j + 1, t)\n",
    "            return ans\n",
    "        \n",
    "        l, r = -1, max(max(lst) for lst in grid)\n",
    "\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            dic = [[0 for _ in range(n)] for _1 in range(n)]\n",
    "            if dfs(0, 0, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        def dfs(i: int, j: int, t: int) -> bool:\n",
    "            if dic[i][j] != 0 or grid[i][j] > t:\n",
    "                return False\n",
    "            dic[i][j] = 1\n",
    "            if i == n - 1 and j == n - 1:\n",
    "                return True\n",
    "            ans = False\n",
    "            if i - 1 >= 0: ans = ans or dfs(i - 1, j, t)\n",
    "            if i + 1 < n: ans = ans or dfs(i + 1, j, t)\n",
    "            if j - 1 >= 0: ans = ans or dfs(i, j - 1, t)\n",
    "            if j + 1 < n: ans = ans or dfs(i, j + 1, t)\n",
    "            return ans\n",
    "        \n",
    "        l, r = -1, max(max(lst) for lst in grid)\n",
    "\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            dic = [[0 for _ in range(n)] for _1 in range(n)]\n",
    "            if dfs(0, 0, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        #水位必须同时淹没这两个平台,时间t也代表高度\n",
    "        DIRECTIONS = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        n = len(grid)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        def dfs(t,x,y,visited):\n",
    "            visited[x][y] = 1\n",
    "            for a,b in DIRECTIONS:\n",
    "                nx = x+a\n",
    "                ny = y+b \n",
    "                if 0<= nx< n and 0<= ny <n  and not visited[nx][ny] and grid[nx][ny]<=t:\n",
    "                    if nx == n-1 and ny == n-1:\n",
    "                        return True\n",
    "                    # visited[nx][ny] = 1\n",
    "                    if dfs(t,nx,ny,visited):\n",
    "                        return True\n",
    "                    # visited[nx][ny] = 0\n",
    "            return False\n",
    "        l = 0\n",
    "        r = n*n #0 <= grid[i][j] < n2\n",
    "        #寻找左边界\n",
    "        # 从一个平台游向四周相邻的任意一个平台 dp得到最少时间\n",
    "        while l < r:\n",
    "            mid = l + (r-l)//2\n",
    "            if grid[0][0]>mid :\n",
    "                l = mid +1\n",
    "                continue\n",
    "            visited = [[0]*n for _ in range(n)]\n",
    "            visited[0][0] = 1\n",
    "            if dfs(mid,0,0,visited):\n",
    "                r = mid\n",
    "                self.flag = False \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "        # 二分\n",
    "        n = len(grid)\n",
    "        left = 0\n",
    "        right = n*n - 1\n",
    "        while left < right:\n",
    "            mid = (right - left) // 2 + left\n",
    "            visited = [[False for _ in range(n)] for i in range(n)]\n",
    "            if grid[0][0] <= mid and self.dfs(grid, 0, 0, visited, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def dfs(self, grid, x, y, visited, threshold):\n",
    "        # 深度优先\n",
    "        n = len(grid)\n",
    "        visited[x][y] = True\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        for dx, dy in directions:\n",
    "            newX = x + dx\n",
    "            newY = y + dy\n",
    "            if self.inArea(newX, newY, n) and not visited[newX][newY] and grid[newX][newY] <= threshold:\n",
    "                if newX == n-1 and newY == n-1:\n",
    "                    return True\n",
    "                if self.dfs(grid, newX, newY, visited, threshold):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def inArea(self, x, y, n):\n",
    "        return x >= 0 and y >= 0 and x < n and y < n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swimInWater(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        visited_index = set()\n",
    "\n",
    "        def can_swim(target_time, x, y):\n",
    "            # 结束条件\n",
    "\n",
    "            if x > len(grid)-1 or x < 0 or y > len(grid[0])-1 or y < 0:\n",
    "                return False\n",
    "            if grid[x][y] > target_time:\n",
    "                return False\n",
    "            if (x,y) in visited_index:\n",
    "                return False\n",
    "            \n",
    "            if x == len(grid)-1 and y == len(grid[0])-1 and grid[x][y] <= target_time:\n",
    "                return True\n",
    "            visited_index.add((x,y))\n",
    "\n",
    "            ans = can_swim(target_time, x-1, y) or can_swim(target_time, x, y-1) or can_swim(target_time, x+1, y) or can_swim(target_time, x, y+1)\n",
    "            if ans:\n",
    "                print(x,y)\n",
    "            return ans\n",
    "                \n",
    "\n",
    "        min_time = min([min(x) for x in grid])\n",
    "        max_time = max([max(x) for x in grid])\n",
    "        \n",
    "        while min_time <= max_time:\n",
    "            target_time = (min_time+max_time) // 2\n",
    "            if can_swim(target_time, 0, 0):\n",
    "                max_time = target_time - 1\n",
    "            else:\n",
    "                min_time = target_time + 1\n",
    "            \n",
    "            visited_index = set()\n",
    "        return min_time\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
